#define _CRT_SECURE_NO_WARNINGS
class Solution {
    string num_str[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public:
    void Combine(const string& digits, int i, vector<string>& vStr, string combine_str)
    {
        if (i == digits.size())
        {
            vStr.push_back(combine_str);
            return;
        }
        int num = digits[i] - '0';
        string str = num_str[num];
        for (auto ch : str)
        {
            Combine(digits, i + 1, vStr, combine_str + ch);
        }
    }
    vector<string> letterCombinations(string digits) {
        int i = 0;
        vector<string> vStr;
        if (digits.empty())
            return vStr;
        string str;
        Combine(digits, i, vStr, str);
        return vStr;
    }
};